package Leetcode100Hot;

import org.junit.Test;

/*
回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：
1 <= s.length <= 1000
s 由小写英文字母组成
 */
public class _23回文子串 {

    @Test
    public void test(){
        System.out.println(countSubstrings("aaa"));
    }

    //DP
    //设dp[left][right]为字符串left 到 right 是否为回文串
    //状态转移
    //当charAt(left) == charAt(right) 判断 dp[left + 1][right - 1]是否为true
    public int countSubstrings(String s) {
        int len = s.length();
        int count = 0;
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
            count++;
        }
        for (int L = 2; L <= len; L++) {
            int left = 0;
            for (left = 0; left < len; left++) {
                int right = left + L - 1;
                if (right >= len) {
                    break;
                }
                if (s.charAt(left) == s.charAt(right)) {
                    if (L <= 3){
                        dp[left][right] = true;
                        count++;
                    }else {
                        if (dp[left + 1][right - 1]){
                            dp[left][right] = true;
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }

    //官解：方法一：中心拓展
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/palindromic-substrings/solutions/379987/hui-wen-zi-chuan-by-leetcode-solution/
     */
    class Solution {
        public int countSubstrings(String s) {
            int n = s.length(), ans = 0;
            for (int i = 0; i < 2 * n - 1; ++i) {
                int l = i / 2, r = i / 2 + i % 2;
                while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                    --l;
                    ++r;
                    ++ans;
                }
            }
            return ans;
        }
    }

}
